Computer-generated graphics techniques for manipulation of three-dimensional objects are being used widely by movie production systems, commercial modelers, and game engines. Computer-generated techniques take a three-dimensional representation of an object and generate a two-dimensional rendering of the object in different positions. These objects are typically represented by a mesh or detail mesh of polygons that defines the surface of the object. A detail mesh can be represented as a set of vertices and connecting edges that define the surface of the object. A triangular mesh M may be represented as (K,V), where K represents the connecting edges and V=(ν1, . . . , νm)T represents the vector of m vertices νiεR3 that each represent a point on the surface of the object.
To generate an animation, an animator typically manipulates the surface of the detail mesh to indicate a new position for target points on the surface of the object being animated. For example, if the object is a person, an animator may animate the person raising their hand by moving the tip of a finger above the person's head. The animator may in general specify a sequence of target positions for points of the person's body to represent an animation of the person. A goal of the computer-generated graphics techniques is to recalculate a new mesh based on the target points so that an accurate two-dimensional representation of the object as it moves can be generated in real time.
It is tedious and impractical to manually specify target positions for all vertices of the detail mesh. A recent mesh deformation technique, referred to as gradient domain mesh deformation or Laplacian deformation, casts mesh deformation as an energy minimization problem that allows more global and complex deformation. Typically, the energy functions used in these techniques contain terms to preserve detail (often through Laplacian coordinates), as well as position-constraint terms to allow for direct manipulation. One energy function is represented as follows:
                              min                      V            d                          ⁢                  (                                                                                                          LV                    d                                    -                                                            δ                      ^                                        ⁡                                          (                                              V                        d                                            )                                                                                                  2                        +                                                                                                CV                    d                                    -                  U                                                            2                                )                                    (        1        )            where L represents the Laplacian operator matrix of Md, LVd represents Laplacian coordinates of the detail mesh before deformation, {circumflex over (δ)}(Vd) represents the Laplacian coordinates of the vertices Vd of the detail mesh after deformation, C represents a positional constraints matrix, and U represents the target positions of the constrained vertices (i.e., vertices under direct manipulation). The left side of the minimization function seeks to minimize the before and after Laplacian coordinates. A Laplacian coordinate represents an average distance between a vertex of the detail mesh and its neighbor vertices. The right side seeks to minimize the difference between the desired position of the constrained vertices and the actual position of the constrained vertices. The left side tends to preserve details of the surface and the right side tends to preserve position constraints. The gradient mesh domain techniques tend to distribute the error over the entire mesh resulting in a high-quality deformation.
Since the storing of such detail meshes may require a vast amount of storage, computer-generated graphics techniques have used subdivision surfaces to reduce the required storage. A subdivision surface is a detail mesh that is generated from a control mesh with much fewer vertices than the detail mesh by subdividing the control mesh according to a subdivision detail function. For example, if the polygons of the control mesh are triangles, then each triangle can be split into four new triangles by adding a vertex to each edge of the triangle. This process of subdividing the mesh can continue until the desired level of subdivision is attained. A displacement map or geometric texture can then be applied to the smooth subdivision surface to get the detail mesh. To represent an object, a computer graphics technique need only store the control mesh and the subdivision detail function, rather than the detail mesh.
To generate an animation for an object represented by a subdivision surface, an animator usually manipulates the vertices of the control mesh. A computer-generated graphics technique then calculates the new vertices for the deformed control mesh using, for example, a Laplacian deformation technique. The technique can then apply the subdivision detail function to the deformed control mesh to generate a deformed detail mesh, which can then be rendered.
Typical techniques for generating an animation for an object represented by a subdivision surface have several disadvantages. For example, these techniques require the animator to manipulate the object using the control mesh, rather using the detail mesh. Such manipulation of the control mesh is not intuitive to an animator because the animator wants to view and manipulate the detail mesh as is done with the deformation of detail meshes. As another example, these techniques do not preserve the surface details of the detail mesh.